package from_0_to_50;

public class Q011_maxArea {

    static int[] bucket= {1,8,6,2,5,4,8,3,7};
    public static void main(String[] args) {
        int maxArea = maxArea(bucket);
        int maxArea1 = maxArea1(bucket);
        System.out.println("maxArea = " + maxArea);
        System.out.println("maxArea1 = " + maxArea1);
    }
    // 求最大面积，关键因素只有两个，底 和 高。（两个元素大小的比较，同增同减，一增一减）
    // 解决思路：双指针 + 两元素一增一减（已建议增）（后面一个思路，不严谨的对双指针用于该题目的正确性）
    static public int maxArea(int[] height) {
        int maxArea = 0;
        int tempArea;
        int left = 0,right = height.length-1;
        while(left < right){
            tempArea = (right - left) * Math.min(height[left],height[right]);
            if(tempArea > maxArea)
                maxArea = tempArea;
            if (height[left] < height[right])
                left++;
            else
                right--;
        }
        return maxArea;
    }
    // 题目优化
    static public int maxArea1(int[] height) {
        int maxArea = 0,tempArea = 0;
        int left = 0,right = height.length-1;
        int bottom = right;
        while(left < right){
            if (height[left] < height[right])
                tempArea = bottom-- * height[left++];
            else
                tempArea = bottom-- * height[right--];
            maxArea = tempArea > maxArea ? tempArea : maxArea;
        }
        return maxArea;
    }
}
